﻿using System.Diagnostics;

namespace DataStructure;

public class TaiLinkListQueue<E> : IQueue<E>
{
    private TaiLinkList<E> list;

    public TaiLinkListQueue() => list = new TaiLinkList<E>();

    //O（1）
    public int Count => list.Count;

    //O（1）
    public bool IsEmpty => list.IsEmpty;

    //O（1）
    public E Dequeue() => list.RemoveFirst();

    //O（1）
    public void Enqueue(E e) => list.AddLast(e);

    //O（1）
    public E Peek() => list.GetFirst();

    //O（1）
    public void Clear() => list.Clear();

    public override string ToString() => $"Queue front {list} tail";

}

class TaiLinkListQueue
{
    static void Main(string[] args)
    {
        int N = 100000;

        ////O(n^2) 只有头指针的链表
        //LinkListQueue<int> linkListQueue= new LinkListQueue<int>();
        //long t1 = TestQueue(linkListQueue, N);
        //Console.WriteLine("LinkListQueue'time: " + t1 + "ms");

        //O(n)  具备头和尾指针的链表
        TaiLinkListQueue<int> taiLinkListQueue = new TaiLinkListQueue<int>();
        long t2 = TestQueue(taiLinkListQueue, N);
        Console.WriteLine("TaiLinkListQueue'time: " + t2 + "ms");
    }

    static long TestQueue(IQueue<int> queue, int n)
    {
        Stopwatch t = new();
        t.Start();

        for (int i = 0; i < n; i++)
            queue.Enqueue(i);
        for (int i = 0; i < n; i++)
            queue.Dequeue();
        t.Stop();
        return t.ElapsedMilliseconds;
    }
}